package cn.nit.algorithm.experiment;

/**
 * @author LXQ
 * @version 1.0
 * @date 2021/6/4 5:57
 */

public class Experiment6 {
    int n = 4;
    int W = 6;
    double maxv = 0;
    int[] x = new int[20];
    Goods[] A = new Goods[5];
    public String totalString="";


    public Experiment6(){
        for (int i = 1; i < 5; i++)
            A[i] = new Goods();
        A[1].no = 3;
        A[1].w = 2;
        A[1].v = 3;
        A[1].p = 1.5;
        A[2].no = 2;
        A[2].w = 3;
        A[2].v = 4;
        A[2].p = 1.3;
        A[3].no = 4;
        A[3].w = 1;
        A[3].v = 1;
        A[3].p = 1;
        A[4].no = 1;
        A[4].w = 5;
        A[4].v = 4;
        A[4].p = 0.8;
        for (Goods g:A){
            System.out.println(g);
            totalString+=g+"<br>";
        }
    }

//    public static void main(String[] args) {
//        Experiment6 experiment = new Experiment6();
//        int[] op = new int[20];
//        experiment.dfs(1, 0, 0, op);
//        experiment.dispasolution();
//    }

    public String runMain(){
        int[] op = new int[20];
        dfs(1, 0, 0, op);
        dispasolution();
        return totalString;
    }

    public double bound(int i, double tw, double tv) {
        i++;
        while (i <= n && tw + A[i].w <= W) {
            tw += A[i].w;
            tv += A[i].v;
            i++;
        }
        if (i <= n) return tv + (W - tw) * A[i].p;
        else return tv;
    }

    public void dfs(int i, double tw, double tv, int op[]) {
        if (i > n) {
            maxv = tv;
            for (int j = 1; j <= n; j++) {
                x[j] = op[j];
            }
        } else {
            if (tw + A[i].w <= W) {
                op[i] = 1;
                dfs(i + 1, tw + A[i].w, tv + A[i].v, op);
            }
            if (bound(i, tw, tv) > maxv) {
                op[i] = 0;
                dfs(i + 1, tw, tv, op);
            }
        }
    }

    public void dispasolution() {
        System.out.println("装入方案:");
        totalString+="装入方案:<br>";
        int sumw = 0, sumv = 0;
        for (int j = 1; j <= n; j++) {
            if (x[j] == 1) {
                sumw += A[j].w;
                sumv += A[j].v;
                System.out.print(A[j].no + "  ");
                totalString+=A[j].no + "  <br>";
            }
        }
        System.out.print("总重量为：" + sumw);
        totalString+="总重量为：" + sumw+"<br>";
        System.out.print("总质量为：" + sumv);
        totalString+="总质量为：" + sumv+"<br>";
    }
}

class Goods {
    int no;
    int w;
    int v;
    double p;

    @Override
    public String toString() {
        return "编号=" + no +
                ", 重量=" + w +
                ", 价格=" + v +
                ", 价格/重量=" + p;
    }
}